package leetcode.LinkedList;

/**
 * 对链表插入排序
 * @author MaoLin Wang
 * @date 2020/2/1114:12
 */
public class _147InsertionSortList {

    public  static ListNode insertionSortList(ListNode head) {

        if (head==null||head.next==null){
            return head;
        }
        ListNode dummy=new ListNode(0);
        ListNode cur=head;
        ListNode next=head.next;
        ListNode temp;
        while (cur!=null){
           if (dummy.next==null){
               cur.next=null;
               dummy.next=cur;
               cur=next;
               next=next.next;
           }else {
               if (cur.val<=dummy.next.val){
                   //当前节点小于dummy最小的节点
                   cur.next=dummy.next;
                   dummy.next=cur;
                   cur=next;
                   next=next==null?null:next.next;
               }else {
                   //当前节点大于dummy最小的节结
                   temp=dummy.next;
                   while (true){
                       if (temp.next==null){
                           cur.next=null;
                           temp.next=cur;

                           break;
                       }
                       if (temp.next.val>cur.val){
                           cur.next=temp.next;
                           temp.next=cur;

                           break;
                       }
                       temp=temp.next;
                   }
                   cur=next;
                   next=next==null?null:next.next;
               }
           }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(3);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(1);
        l1.next.next.next = new ListNode(6);
        l1.next.next.next.next = new ListNode(5);
        ListNode node = insertionSortList(l1);
        ListNode.printNode(node);
    }
}
